﻿//#define TRACE_ANAGRAMS
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Net;
using System.Text.RegularExpressions;

namespace ProjectEulerSolutions
{
    /*
     * 
By replacing each of the letters in the word CARE with 1, 2, 9, and 6 respectively, we form a square number: 1296 = 362. What is remarkable is that, by using the same digital substitutions, the anagram, RACE, also forms a square number: 9216 = 962. We shall call CARE (and RACE) a square anagram word pair and specify further that leading zeroes are not permitted, neither may a different letter have the same digital value as another letter.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, find all the square anagram word pairs (a palindromic word is NOT considered to be an anagram of itself).

What is the largest square number formed by any member of such a pair?

NOTE: All anagrams formed must be contained in the given text file.

     * */
    class Problem98 : IProblem
    {
        public string Calculate()
        {
            WebClient wc = new WebClient();
            string input = wc.DownloadString("http://projecteuler.net/project/words.txt");

            var words = Regex.Matches(input, "[A-Z]+").Cast<Match>().Select(x => x.Value);

            Dictionary<string, List<string>> anagrams = new Dictionary<string, List<string>>();

            foreach (string word in words)
            {
                string ordered = new string(word.OrderBy(x => x).ToArray());
                if (anagrams.ContainsKey(ordered))
                {
                    anagrams[ordered].Add(word);
                }
                else
                {
                    anagrams.Add(ordered, new List<string>());
                    anagrams[ordered].Add(word);
                }
            }

#if TRACE_ANAGRAMS
            foreach (var value in anagrams.Values)
            {
                if (value.Count > 1)
                {
                    foreach (var s in value)
                    {
                        Console.Write(s + " ");
                    }
                    Console.WriteLine();
                }
            }
#endif

            int maxSquare = 0;
            int maxLength = 0;


            var q = anagrams.Where(x => x.Value.Count == 2).OrderByDescending(x => x.Key.Length).Select(x => x.Value);

            foreach (var anagram in q)
            {
                int length = anagram[0].Length;
                if (length < maxLength)
                    return maxSquare.ToString();

                int min = (int)Math.Sqrt(Math.Pow(10, length - 1));
                int max = (int)Math.Sqrt(Math.Pow(10, length + 1));
                for (int i = min; i <= max; i++)
                {
                    Dictionary<char, int> map = new Dictionary<char, int>();
                    var digits = CommonFunctions.GetDigits(i * i);

                    if (digits.Count < anagram[0].Length)
                        continue;

                    if (digits.Count > anagram[0].Length)
                        break;

                    bool match = true;

                    foreach (char c in anagram[0])
                    {
                        if (map.ContainsKey(c))
                        {
                            if (digits[digits.Count - 1] != map[c])
                            {
                                match = false;
                                break;
                            }
                            else
                            {
                                digits.RemoveAt(digits.Count - 1);
                            }
                        }
                        else if (map.Values.Contains(digits[digits.Count - 1]))
                        {
                            match = false;
                            break;
                        }
                        else
                        {
                            map.Add(c, digits[digits.Count - 1]);
                            digits.RemoveAt(digits.Count - 1);
                        }
                    }

                    if (!match)
                        continue;

                    List<int> second = new List<int>();
                    foreach (char c in anagram[1])
                        second.Add(map[c]);

                    if (second[0] == 0)
                        continue;

                    int secondNumber = 0;
                    foreach (int n in second)
                    {
                        secondNumber *= 10;
                        secondNumber += n;
                    }

                    double root = Math.Sqrt(secondNumber);
                    if (root == (int)root)
                    {
                        int greaterSquare = Math.Max(secondNumber, i * i);
                        if (greaterSquare > maxSquare)
                        {
                            Console.WriteLine(anagram[0] + " " + anagram[1]);
                            Console.WriteLine(Math.Min(secondNumber, i * i));
                            maxSquare = greaterSquare;
                            maxLength = length;
                        }
                    }
                }
            }



            return maxSquare.ToString();
        }
    }
}
